package leetcode;

import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.Stack;
public class LeetCodeMain78 {
    public boolean isPalindrome(ListNode head) {
         if (head.next==null){
             return true;
         }
        ListNode fast=head;
        ListNode slow=head;
        while (fast!=null&&fast.next!=null){
            slow=slow.next;
            if(fast.next.next==null){
                fast=fast.next;
            }
            else{
                fast=fast.next.next;
            }
        }
         ListNode n3=slow.next;
         while (n3!=null){
             ListNode n4=n3.next;
             n3.next=slow;
             slow=n3;
             n3=n4;
         }
         while (head!=fast&&head.next!=fast){
             if (head.val!=fast.val){
                 return false;
             }
             head=head.next;
             fast=fast.next;
         }
         if (fast.val!=head.val){
             return false;
         }
         return true;
    }
    public int longestConsecutive(int[] nums) {
        int length=nums.length;
        Set<Integer> set=new HashSet<>();
        for (int num:nums) {
            set.add(num);
        }
        int max=0;
        for (int num:set) {
            if (!set.contains(num-1)){
                int max1=1;
                int n=num;
                while (set.contains(n+1)){
                    n++;
                    max1++;
                }
                max=Math.max(max,max1);
            }
        }
        return max;
    }
    public int longestValidParentheses(String s) {
        if(s.length()==0||s==null||"".equals(s)){
            return 0;
        }
        int length=s.length();
        int[] dp=new int[length];
        int max=0;
        for (int i = 1; i < length; i++) {
            if (s.charAt(i)==')'){
                if (s.charAt(i-1)=='('){
                    dp[i]=(i>=2?dp[i-2]:0)+2;
                }else if (i-dp[i-1]>0&&s.charAt(i-dp[i-1]-1)=='('){
                    dp[i]=dp[i-1]+(i-dp[i-1]>=2?dp[i-dp[i-1]-2]:0)+2;
                }
            }
            max=Math.max(max,dp[i]);
        }
        return max;
    }
}
